import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 姚东名
 * Date: 2024-10-08
 * Time: 17:21
 */
public class Test {
    //随即链表的复制
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            map.put(cur, node);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    public static void main4(String[] args) {
        char[] ch = new char[]{'a', 'b', 'c'};
        String s1 = new String(ch);
        String s2 = "abc";
        System.out.println(s1 == s2);// false
    }

    public static void main(String[] args) {
        char[] ch = new char[]{'a', 'b', 'c'};
        String s1 = new String(ch);
        s1.intern();
        String s2 = "abc";
        System.out.println(s1 == s2);// true
    }
    public static void main3(String[] args) {
        String str1 = "hello";
        String str2 = "hello";
        System.out.println(str1 == str2); //true

        String str3 = new String("hello");
        String str4 = new String("hello");
        System.out.println(str3 == str4); //false
    }
    //前K个高频单词
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        //统计每个单词出现的次数
        for (String word : words) {
            if (map.get(word) == null) {
                map.put(word, 1);
            } else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }
        //创建一个小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //假如元素频率相同，就比较其字典顺序：按照字典顺序排序
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                //根据频率来比较
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //遍历map
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                //首先比较频率
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (top.getValue().compareTo(entry.getValue()) == 0) {
                    //当二者的频率相同时，就比较其字符顺序排序
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        //逆置打印顺序
        List<String> list = new ArrayList<>();
        //把前K个元素放到顺序表中
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> ret = minHeap.poll();
            list.add(ret.getKey());
        }
        //逆置
        Collections.reverse(list);
        return list;
    }

    //旧键盘坏掉的键帽
    public static void func(String str1,String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        HashSet<Character> set2 = new HashSet<>();
        for (int i = 0; i < str2.length(); i++) {
            char ch = str2.charAt(i);
            set2.add(ch);
        }
        HashSet<Character> set1 = new HashSet<>();
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if(!set2.contains(ch) && !set1.contains(ch)) {
                //!set1.contains(ch) -> 是为了不把重复的字符放到set1中
                set1.add(ch);
                System.out.print(ch);
            }
        }
    }
    public static void func1(String str1,String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();

        HashSet<Character> setAct = new HashSet<>();
        for (int i = 0; i < str2.length(); i++) {
            char ch = str2.charAt(i);
            setAct.add(ch);
        }

        HashSet<Character> setBroken = new HashSet<>();

        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if(!setAct.contains(ch) && !setBroken.contains(ch)) {
                setBroken.add(ch);
                System.out.print(ch);
            }
        }
    }

    public static void main2(String[] args) {
        func("7_This_is_a_test", "hs_s_a_es");
        func1("7_This_is_a_test", "hs_s_a_es");
    }

    //宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            char ch = jewels.charAt(i);
            set.add(ch);
        }
        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            char ch = stones.charAt(i);
            if (set.contains(ch)) {
                count++;
            }
        }
        return count;
    }
    //计算数组中单词存在的个数
    public static Map<String, Integer> countWord(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);//第一次放入
            } else {
                int val = map.get(s);
                map.put(s, val + 1);
            }
        }
        return map;
    }

    //只出现一次的数字
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                set.remove(nums[i]);
            } else {
                set.add(nums[i]);
            }
        }
        //遍历原数组，在set集合中找唯一的数字
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }

    public static void main1(String[] args) {
        String[] words = {"hello", "abc", "hello", "def", "this", "this", "this"};
        Map<String, Integer> map = countWord(words);
        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
        for (Map.Entry<String, Integer> entry : entrySet) {
            System.out.println("Key: " + entry.getKey() + " val: " + entry.getValue());
        }
    }
}
